A. Field of the Invention
This invention relates to the field of data communication and data-over-cable systems compliant to the Data-Over-Cable Service Interface Specification (DOCSIS) standard. More particularly, the invention relates to a method of reducing delay in a cable system. The method involves communicating packet arrival times or measurements of latency between grants of bandwidth and packet arrival times at the cable modem to a cable modem termination system, which responsively adjusts the timing of grants of bandwidth.
The invention will be described in several contexts, one of which is a method for granting upstream channel bandwidth to cable modems for transmission of Transmission Control Protocol (TCP) acknowledgments. The method of the invention improves the performance or throughput of TCP connections between the cable modems and a Cable Modem Termination System (CMTS).
B. Description of Related Art
With the explosive growth of the Internet, many customers have desired to use the larger bandwidth of a cable television network to connect to the Internet and other computer networks. Cable modems, such as those provided by 3Com Corporation of Santa Clara, Calif., and others offer customers higher-speed connectivity to the Internet, an intranet, local area networks (“LANs”), and other computer networks via cable television networks. These cable modems currently support a data connection to the Internet and other computer networks via a cable television network with a data rate of up to 30+ Mbps, which is a much larger data rate than can be supported by a modem used over a standard telephone line.
Data-over-cable systems may serve many cable modems simultaneously. A cable modem receives and transmits data in the form of digitally encoded radio frequency transmissions, which typically travel to and from the cable modem on, for example, coaxial cable. Also, the data-over-cable system consists of many branches from a common trunk, each branch serving a distinct group of cable modems, and the branches themselves may further divide into sub-branches. Thus the propagation of radio frequency signals to and from the cable modem often follows a circuitous and convoluted path. Transmissions from the cable modem are terminated in a cable system head-end by a device known as a Cable Modem Termination System or CMTS.
Background information related to cable modem systems in general is described in the Data-Over-Cable Service Interface Specifications (“DOCSIS”)—Radio Frequency Interface Specifications, issued by Cable Television Laboratories, Inc. This document, known to persons working in the art, is incorporated by reference herein in its entirety. The DOCSIS standard specifies a collection of layers of communication protocols to be used in cable networks. These specifications are commonly referred to as “the DOCSIS standard”. The DOCSIS standard is comprised of several specifications, among them, the RFI specification referred to above which describes the Radio Frequency Interface, in other words the operations of the Physical, Sub-Convergence, Media Access Control, Network and Application layers inside the Cable Network.
The cable network offers customers higher-speed connectivity to the Internet and other computer networks via a cable modem. The cable modem is an interface between an end-station and the cable network. The end-station or the terminal is a device on the cable network, for example a personal computer, which communicates over the cable network. The cable modem enables the station to send and receive data from the cable network. As multiple cable modems may reside on the same coaxial cable, each contends for a share of the available bandwidth. Therefore, the cable television network is a shared access medium.
In the cable television network, transmissions originating from cable modems, referred to as “upstream traffic”, and transmissions directed to cable modems, referred to as “downstream traffic”, are carried on different frequencies. In the downstream direction, the data is transmitted through the shared medium. Medium Access Control (MAC) layer addressing ensures that the data is picked up and received by its intended target station. In the upstream direction, the CMTS divides time into regions, and communicates these regions to the cable modems by means of “MAP” messages transmitted on the downstream. The process of allocating portions of the upstream bandwidth to specific cable modems, so that they may transmit data on the upstream is commonly referred to as “Scheduling”. The DOCSIS standard provides several methods of scheduling:
1.) Best Effort Service                A cable modem wishing to transmit data on the upstream transmits data requests to the CMTS, in what are called contention regions. The CMTS transmits data grants to the cable modems, and the cable modems use the regions allocated to them in the data grants, to transmit their data.        
2.) Unsolicited Grant Service (UGS)                During the initialization and registration of the cable modem, the CMTS establishes UGS service to that modem by periodically transmitting data grants to that specific modem. The grants are transmitted whether the modem uses them to transmit data or not.        
3.) Unsolicited Grant Service with Activity Detection (UGS-AD)                Very similar to the UGS service, UGS-AD scheduling service waits for the cable modem to request a data grant. The CMTS then grants the requested data grant, and immediately starts a UGS service to the cable modem. When the CMTS detects that the cable modem is no longer using the data grants that it is being sent, the CMTS stops the UGS service.        
4.) Real-Time Polling Service (RTPS)                Normally, in every MAP message, the CMTS schedules contention regions. These regions are open for every cable modem, and those cable modems which wish to transmit data, use these regions to transmit their requests. As the name implies, however, these are contention regions and more than one cable modem may transmit during this period. In that case, the CMTS will not hear the request, and therefore does not send data grants to the cable modems. When the cable modems detect the time-out for the data grant, they randomly back-off and use a different contention region to re-transmit their requests. It is, however, possible for the CMTS to transmit a unicast request region to a specific cable modem. This region takes up much less bandwidth than sending Unsolicited Grant Service, and therefore is more bandwidth efficient. The practice of scheduling periodic unicast request regions for specific modems is called “Real Time Polling” service.        
5.) Non-real-time Polling Service(nRTPS)                This service is very similar to the RTPS service, except that the periodicity of the unicast requests in the nRTPS is much less stringent than the RTPS.        
TCP
Cable modems compliant with the DOCSIS standard use TCP, or Transmission Control Protocol. TCP is a part of the Internet standard protocol suite generally referred to as the “TCP/IP” standard. It is fully defined in the IETF standards document RFC793, part of STD0007, incorporated by reference herein.
TCP is a transport layer protocol. It is also a connection oriented protocol. In other words, when TCP is employed as the transport layer of a transmission, the two hosts exchanging data first establish a connection. During the establishment of the connection, and later on as well, the two hosts exchange configuration data in order to most efficiently utilize the connection between them. After this, the hosts start exchanging data. At the end, the two hosts go through an explicit disconnect handshake, in order to tear down the TCP connection between them. During the transfer of data, TCP aims to guarantee delivery of the data packets from one host to the other. Towards this purpose, the host that receives the packet acknowledges the packet's reception to the host which sent the packet. The host sending the packet keeps track of the acknowledgments (ACKs) it is receiving and if it detects that there are one or more packets which were not acknowledged by the receiving host, the sending host re-transmits these packets. Thus, TCP guarantees zero packet loss during the data exchange. Depending on the implementation, TCP hosts may ACK every packet they receive, they may ACK every other packet they receive or they may employ other ACK strategies.
TCP employs the concept of a flow control window. This window determines the number of bytes that the sending host may transmit to the receiving host before the sending host needs to pause and wait for an acknowledgment. In other words, this window determines the number of unacknowledged bytes that may be outstanding at any one time. If that number is reached, transmission must pause until one or more packets are acknowledged by the receiving host.
The flow control model that is used by TCP is a dynamic one, such that the size of the window is increased and decreased in response to the source's perception of the performance of the sink and the performance of the network. At the beginning of a connection, TCP goes through the slow-start phase, with a small window size. The window size is increased as ACKs are received from the sink (destination). At the beginning, the window size is increased exponentially, until the window size reaches a size referred to a “ssthresh” (slow start threshold), after which, the window size is increased linearly. During the exponential period, every ACK received from the sink doubles the window size, whereas during the linear period, every ACK received from the sink increases the window size by the inverse of the current window size (1/└w┘). TCP will decrease its window size when it detects loss of ACKs. Of the two widely used versions of TCP, TCP-Tahoe detects missing ACKs via timeouts, and reacts to this situation by setting the flow control window back to 1, halving the value of ssthresh and re-entering the exponential phase of the flow management. TCP-Reno, on the other hand, detects missing ACKs via timeouts and duplicate ACKs. If missing ACKs are detected via a timeout, TCP-Reno behaves identical to TCP-Tahoe, however, when duplicate ACKs are detected (three, to be more precise), TCP-Reno halves the ssthresh and the current flow control window, which results in the TCP connection going into the linear phase of the flow control management scheme.
Thus, from the above discussion, it will be apparent that the throughput of a TCP session in an asymmetric system, as is typical with cable modem Internet connections, is largely dependent on the slower of the two links, both during “healthy” bulk transfer and during recovery from loss. We also note that data-over-cable systems, while less so than wireless systems, are quite prone to loss in the upstream because of noise in the HFC plant. The throughput of a TCP connection depends not only on how fast the sending host can transmit data to the receiving host, but also on how fast the receiving host acknowledges back to the sending host.
During a TCP session, at the point when the flow control window is opened to its maximum size, the throughput of the system cannot exceed w/RTT packets/sec, where RTT is the Round Trip Time of the system. See S. Keshav, “An Engineering Approach to Computer Networking: ATM Networks, the Internet and the Telephone Network”, Addison Wesley Publishing Co., July 1997. Intuitively, we can conclude that decreasing the round trip time will have a direct effect on the throughput of a TCP connection, even if the decrease is gained on that half of the connection which only carries the ACKs.
As described in T. V. Lakshman et al., “Performance Analysis of Window-Based Flow Control Using TCP/IP: The Effect of High Bandwidth-Delay Products and Random Loss”, IFIP Transactions C-26, High Performance Networking V, North-Holland 1994 pp. 135–150, the throughput of a TCP connection will decrease in proportion to p(Rμ)2, with p being the probability of packet loss and Rμ the bandwidth-delay product. The two components of Rμ are R, the round-trip time in seconds and μ, the bottleneck service rate along the path. In a DOCSIS system, μ will be the speed of upstream link, or the speed of the link between the cable modem and the end-station, whichever is the slowest.
In accordance with the present invention, we describe one method to decrease the round trip time R, by decreasing the delay on the upstream link between the cable modem and the CMTS. In addition to improving the throughput of the system, this decrease will also lessen the impact of packet loss on the performance of TCP, by increasing the speed with which the TCP connection recovers back to the larger window sizes. It will be noted that that this improvement will be proportional to the square of the decrease we gain in the round trip time, in other words the improvement will be proportional to R2. One principal aspect of how this improvement is achieved is provided by the inventive method of communication of TCP ACK packet arrival times at the cable modem to the cable modem termination system
There are a number of existing methods proposed to alleviate the effects of a slow ACK path in a TCP connection.                1.) ACK Spoofing: TCP ACK spoofing entails the transmission of TCP ACKs by a network entity other than the station that is receiving the data which the ACKs are for. This is a method that has been used in deployed products by several vendors, although most of the time it is used in products that connect one station to another, in other words point-to-point connections. The reason for this is that TCP ACK spoofing requires the spoofing host to keep track of the TCP connection that it is providing ACKs for, firstly so as to know when and which packets require an ACK, but also so that when the station which is the receiver for the data, needs a re-transmission and therefore sends an ACK with a sequence number indicating the request for a re-transmission, the spoofing entity can realize the request, and send the appropriate ACK to facilitate the re-transmission. Hence, TCP ACK spoofing gets incredibly complex and memory intensive as the potential number of simultaneous TCP connections increases. Thus, it is not a very suitable method for a cable network with thousands of subscribers.        2.) ACK Filtering (Collapsing ACKs): Since TCP ACKs are cumulative, it is possible to filter out ACKs without harming a TCP connection. However, the filtering entity needs to be intelligent so as to not starve the source. This method can be applied at the sink itself, however it requires modification to the TCP stack at the network layer, or it could be done at a driver layer in which case the driver would have to be intelligent about multiple simultaneous connections. ACK Filtering could also be implemented at the cable modem, which then would have to be aware of the individual TCP connections going through it. See the Keshav reference cited above.        3.) Congestion Window Based Schemes: These schemes employ methods for the sink to increase/decrease the number of ACKs it transmits depending on the past, current or estimated size of the congestion window parameter Cwnd. These methods require modifications to the protocol stack on the source, the sink, or both, and thus is a less attractive solution.        4.) Header Compression: Header compression certainly helps in reducing the bandwidth required by transmissions on the upstream. Within the DOCSIS standard, it does not, however, help reduce the delay incurred by the ACK packets, since the cable modem still has to go through the request-grant process in order to secure bandwidth (albeit less bandwidth) for the packet. See V. Jacobsen, “Compressing TCP/IP Headers for Low-Speed Serial Links”, IETF RFC 1144, February 1990.        
Furthermore, DOCSIS provides a method which relates to this issue, known as concatenation. Concatenation allows the cable modem to concatenate several smaller packets into one large packet at the cable modem, and request bandwidth for and transmit only the single, larger packet. While this method definitely helps alleviate upstream congestion at the cable modem, it only takes effect after the fact. In terms of the present discussion, concatenation would take effect only after several ACKs had piled up at the cable modem. In other words, concatenation does not help reduce the delay which a single ACK packet incurs in the upstream direction.
The asymmetric nature of the DOCSIS standard also affects latency and delay for TCP connections. As was explained above, the upstream transmissions from the cable modem to the CMTS and the downstream transmissions from the CMTS to the cable modem are carried out on two different frequencies. Although the two different frequencies are carried on the same piece of coaxial cable at the termination point at the cable modem, because they are carried in two separate frequencies, the transmissions are physically isolated and employ different modulation types, resulting in distinct characteristics with regards to bandwidth and delay.
Insofar as bandwidth is concerned, the physical layer characteristics of upstream and downstream transmissions vary greatly in the DOCSIS standard. So do the data link layer characteristics, especially in the MAC sublayer. At the physical layer, upstream transmissions are modulated as QPSK or QAM16 signals, whereas the downstream transmissions are modulated as QAM64 or QAM256 signals. Whereas QPSK and QAM16 modulation methods achieve maximum bit rates of roughly 2.5 megabits per second (Mbps) and 10 Mbps respectively, QAM64 and QAM256 modulation methods achieve bit rates of 28 Mbps and 39 Mbps respectively.
Insofar as delay is concerned, the interleaver at the CMTS adds latency (delay) to the transmission of packets. Depending on the combination of interleaver and modulation type, this latency varies from 140 microseconds (usec) to 4.0 milliseconds (msec). In the upstream direction, the symbol rate used in the modulation of the signal, introduces different amounts of latency (delay) to the reception of the packet by the CMTS as well. Both directions also have a transmission delay due to the transmission media of up to about 1 ms.
The significant portion of the delay in a DOCSIS system, however, is introduced by the DOCSIS MAC layer mechanism for the upstream link. A cable modem wishing to transmit data on the upstream needs to go through a request-grant sequence. The requests for bandwidth are generally transmitted in contention regions and may collide with requests from other cable modems. However, since transmissions from one cable modem cannot be heard by another, a cable modem cannot listen on the line in Ethernet fashion. Rather it detects request collisions by inferring that the CMTS has not heard its request. Such a collision in a DOCSIS system results in significant delays. After the CMTS hears the request, it schedules bandwidth for the cable modem at a time in the future—this delay is determined by taking current time and adding to it the latency internal to the CMTS, the latency on the wire (propagation delay) and the latency in the cable modem. A cable modem which has secured bandwidth from the CMTS, and which also needs to request more bandwidth, can do so by “piggybacking” the request onto the data packet. This action eliminates the collision-prone request, but the CMTS still has to grant the modem bandwidth for the second packet.
An example will illustrate the various TCP and MAC aspects of delay. Consider the transmission of a single data packet from an File Transfer Protocol (FTP) server connected to the network side of the CMTS, to an end station (e.g., personal computer) connected to a cable modem on the cable network, and the transmission of a TCP ACK from that station to the FTP server. The FTP server transmits the data to the CMTS at the speed allowed by the physical characteristics of the network connection and the congestion on that network. Let us assume that this is only a 10 Mbps Ethernet connection. The CMTS transmits that packet to the cable modem, at the speed allowed by the downstream modulation in use, with the latency introduced by the interleaver in use. The cable modem transmits that packet to the end station at the speed allowed by the network connection between the cable modem and the station, let's say a 10 Mbps Ethernet connection.
The end station now transmits a TCP ACK packet back to the FTP server. The ACK packet crosses the 10 Mbps Ethernet connection and arrives at the cable modem. The cable modem now needs to transmit that packet to the CMTS so that it can be delivered to the FTP server. FIG. 1 shows the nine steps numbered 1–9 of a bandwidth request/grant cycle for cable modems, with no collisions. As shown in FIG. 1, the cable modem must first request a data grant, at step 1. For this purpose, the cable modem selects one of the contention regions of the upstream bandwidth and transmits a request packet. After a MAP interval of 1–4 ms, the modem receives the MAP at step 2. There is some period of delay of 0–4 ms within the REQ opportunity occurs. The modem sends a bandwidth request, step 3. After processing of the request at step 4, the CMTS sends a MAP with a grant of bandwidth to the modem at step 5. There is a further delay until the grant opportunity occurs, step 6. Eventually, the modem transmits its ACK packet at step 7, with some transmission delay incident thereto. After receipt of the ACK at the cable modem, step 8, and after some processing delay, the ACK is passed on by the CMTS to the server or destination at step 9. The total period of the delay, assuming no collisions is between 4 and 33 milliseconds.
There is a possibility of a collision on the bandwidth request packet in the upstream path. Specifically, this packet may collide with one or more other request packets transmitted by other cable modems on the cable network. If it does, the cable modem will recognize this fact only by following the bandwidth allocations of the CMTS—if the MAP messages (which allocate bandwidth in the upstream) indicate that requests more recent than this cable modem's request have already been processed, the cable modem will determine that a collision has occurred. In that case, the cable modem backs off a random amount of time and transmits another request, in another request region. Steps 2–6 of FIG. 1 are repeated for each collision cycle, with a delay of 2–33 ms per collision cycle. Let us say that the request is received by the CMTS. At this point, the CMTS will schedule the data transmission of this cable modem, at a point in the future. The time elapsed per collision cycle is determined by several factors: utilization of upstream bandwidth, the frequency with which the scheduler can transmit maps and the latency of map transmissions as dictated by the processing time of the CMTS, the modulation and interleaver type in use on the downstream, and some guard time for processing overhead at the cable modem.
Even with collisions the cable modem will eventually receive the data grant, and will transmit the data on the upstream at the allocated time. Because of the different speeds of the upstream and downstream links, data transmission can take from 3 to 20 times longer in the upstream direction than the downstream direction. Taking all of this into account, the request/grant time for a modem can take 5 to 35 ms with no request collision, or if there are collisions, an additional 2 to 33 ms per collision.
The result of the upstream data delay relative to the downstream data, is that ACK messages get queued up at the cable modem, as shown in FIG. 2. FIG. 2 is a drawing showing the timing sequence of message between the FTP server and the host and cable modem in the present example. The FTP server, which sends data to the host or end station via the large bandwidth downstream pipe, will send a full window's worth of data (in multiple packets) to the host and then wait for an ACK message from the host. The host in turn will generate multiple ACK messages as it begins receiving the data packets. These messages get sent to the cable modem, which begins the request/grant process in order to send the data upstream. Because this process is longer than the rate at which the host will send ACK messages for the first set of data, the ACK messages will begin to get backed up at the cable modem. This means that the server cannot send any more data to the host until it gets an ACK message. The net result is that ACK messages are slowly cleared out of the queue and therefore the server ends up sending only one or two packets at a time. This essentially drives the “available” TCP window size at any time to the size of few packets—far short of what is theoretically possible. The result appears to the user as a slow connection.
The above discussion and illustrative example of FIG. 2 indicates a delay problem with a DOCSIS-compliant data-over-cable system that can substantially detract from the performance and efficiency of the system. The present invention provides methods and apparatus by which TCP throughput in a DOCSIS-type implementation is increased, thereby improving the efficiency of a data-over-cable system. The present invention has the advantage that it requires the modification of only DOCSIS-specific modules of the CMTS, or in alternative embodiments of the cable modems, but which does not prohibit the co-existence of implementations of other existing solutions, such as the ACK spoofing or ACK filtering approaches described previously. Furthermore, no modification of the TCP stacks in the host or end station is required. The invention is transparent to the user; the only effect that they see is a faster connection.